﻿#pragma once
#include<iostream>
#include<string>
#include<assert.h>
#include<thread>
#include<mutex>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<unordered_map>
#include <atomic>
#include"ObjectMemoryPool.h"

using std::cout;
using std::endl;

const size_t MAX_BYTES = 256 * 1024; // 256KB
const size_t FREE_LIST_NUM = 208;  //Thread Cache的哈希桶有208个自由链表
const size_t Span_LIST_NUM = 208;  //Central Cache的哈希桶也有208个自由链表
const size_t PAGENUM = 129;      //PageCache的哈希桶的木板数量 （不使用0号下标)
const size_t PAGE_SHIFT = 13;


#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
//#elif // linux
#endif

#ifdef _WIN32
#include<Windows.h>
#elif 
   //linux ...

#endif


// windows和Linux下如何直接向堆申请页为单位的大块内存：
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下 brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

//向系统归还内存
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else //linux
	// sbrk unmmap等
#endif
}


//提供一个获取内存块前4/8个字节（里面存的是下一个内存块起始地址）的功能:
// 加一个static,每个包含Common.h的源文件都会有一份自己的NextObj函数(属于自己的内部链接)

static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//管理每个小内存块对象的自由链表
class FreeList {
public:
	FreeList() :_freelist(nullptr),_size(0) {

	}
	void Push(void* obj) //新增一个内存块
	{
		assert(obj); //obj不能为空

		//头插即可，和定长内存池那里一样
		NextObj(obj) = _freelist;
		_freelist = obj;

		_size++;
	}

	//新增num个内存块(Central Cache给的)
	void PushMany(void* start, void* end, size_t num)
	{
		//将该多个相连的内存块头插进当前自由链表

		//1.取出end指向的内存块的头几个字节，然后存_freelist
		NextObj(end) = _freelist;
		//2.新的头
		_freelist = start;
		_size += num;

		//验证start到end的内存块个数是否真的是num个
		//int i = 0;
		//void* ptr = start;
		//while (ptr)
		//{
		//	ptr = NextObj(ptr);
		//	i++;
		//}
		//
		////条件断点
		//if (num != i)
		//{
		//	int x = 0;
		//}
		
	}

	size_t Size()
	{
		return _size;
	}
	bool Empty()
	{
		if (_freelist == nullptr) //当前自由链表没有内存块
		{
			return true;
		}
		return false;
	}
	void* Pop()  //返回一个内存块
	{
		assert(_freelist); //_freelist不能为空

		//头删即可，和定长内存池那里一样
		void* obj = _freelist;
		_freelist = NextObj(_freelist);

		_size--;
		return obj;
	}
	//取出num个内存块还给CentralCache
	void PopRange(void*& start, void*& end, size_t num)
	{
		assert(num >= _size);
		start = _freelist;
		end = start;

		for (int i = 1; i <= num - 1; i++) {  //end走num-1步就能取出num个内存块
			end = NextObj(end);
		}
		//取完之后，当前木板的_freelist要更新指向
		_freelist = NextObj(end);

		//end的后面置空
		NextObj(end) = nullptr;
		//目前剩下的内存块
		_size -= num;
	}
	size_t& MAXNUM()
	{
		return _maxnum;
	}
	~FreeList() {

	}
private:
	void* _freelist;
	size_t _maxnum = 1;  //向central cache申请这种FreeList下的内存块时，每次申请的最大数量
	size_t _size = 0; // 当前FreeList下挂了多少个内存块
};


class SizeClass {
public:
	//1. 内存块大小的对齐
	static size_t Alignment(size_t size, size_t alignNum) // size: 对齐前大小，alignNum: 对齐数
	{
		size_t After_Align_size = 0; //对齐之后的内存块大小
		if (size % alignNum != 0)
		{
			After_Align_size = (size / alignNum + 1) * alignNum;
		}
		else
		{
			After_Align_size = size;
		}
		return After_Align_size;
	}

	static size_t Align_Upwords(size_t size) //向上对齐
	{
		if (size <= 128)
		{
			return Alignment(size, 8);
		}
		else if (size <= 1024)
		{
			return Alignment(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return Alignment(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return Alignment(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return Alignment(size, 8 * 1024);
		}
		else  //申请大于256KB的内存
		{
			//以页（8KB）为单位对齐
			return Alignment(size, 1 << PAGE_SHIFT); //2^13 = 8KB

			assert(false);
		}
	}

	//2.内存块与哈希桶的下标映射关系
	static size_t _index(size_t align_size, size_t alignNum) //alignNum是对齐数
	{
		return align_size / alignNum - 1;
	}

	static size_t Index(size_t align_size) // align_size 即对齐之后的内存块大小
	{
		assert(align_size <= MAX_BYTES);

		if (align_size <= 128)
		{
			return _index(align_size, 8);
		}
		else if (align_size <= 1024)
		{
			return _index(align_size - 128, 16) + 16;
		}
		else if (align_size <= 8 * 1024)
		{
			return _index(align_size - 1024, 128) + 72;
		}
		else if (align_size <= 64 * 1024)
		{
			return _index(align_size - 8 * 1024, 1024) + 128;
		}
		else if (align_size <= 256 * 1028)
		{
			return _index(align_size - 64 * 1024, 8 * 1024) + 184;
		}
	}

	//3. 线程每次向central cache申请内存块的数量的计算规则
	static size_t NumMoveSize(size_t size) //size是单个内存块(对齐后)的大小
	{
		if (size == 0)
			return 0;
		// [2, 512]，⼀次批量移动多少个对象的(慢启动)上限值
		// ⼩对象⼀次批量上限⾼
		// ⼩对象⼀次批量上限低

		int num = MAX_BYTES / size;  //MAX_BYTES定义为256KB

		//(1)如果size很大，大到计算出的num < 2的话，就给两个size
		if (num < 2)
			num = 2;
		//(2)如果size很小，小到计算出的num > 512的话，就给512个size
		if (num > 512)
			num = 512;
		//(3)如果num处于2~512之间，直接给num个size

		return num;
	}

	//4. CentralCache层向PageCache层申请多少个页的计算规则
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;

		return npage;
	}

private:

};

//CentralCache和PageCache层都用到了Span结构体
// (1) CentralCache 使用它内部的_freelist来管理连接小的内存块
// 
// (2）PageCache 使用它来管理大块内存，这个大块内存由特定数量的页构成。
//  
struct Span {
	PAGE_ID _pageid = 0; // 大块内存起始页的页号
	size_t _n = 0; //页的数量

	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _objSize = 0;  //在CentralCache层切好的小块内存的大小（也可能是直接向堆申请的大块内存
	                      // 反正设计这个变量的目标是为了回收内存时，不需要传申请的内存的size参数

	size_t _useCount = 0;  //分配了几个内存页给ThreadCache

	void* _freelist = nullptr;  //将这些小块内存页连接管理起来
	bool _isUse = false;   //是否在被CentralCache使用
};


// 管理所有的Span
// 带头双向循环链表
// SpanList是Central Cache的哈希桶的一块木板
class SpanList {
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	//当Central Cache的哈希桶某个位置没有Span时，就需要向Page Cache申请
	// Page Cache返回一个Span后：在pos位置前插入该newSpan
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		//pos的前一个Span:
		Span* pre = pos->_prev;

		pre->_next = newSpan;
		newSpan->_prev = pre;
		newSpan->_next = pos;
		pos->_prev = newSpan;

	}
	//"删掉"pos指向的Span：将该Span从对应的SpanList上去掉
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head); //不能删掉哨兵Span

		Span* pre = pos->_prev;
		Span* next = pos->_next;

		pre->_next = next;
		next->_prev = pre;
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	bool Empty()
	{
		return _head->_next == _head; //如果哨兵自己指向自己，那么就为空
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}

	//头插来自PageCache的Span
	void PushFront(Span* newspan)
	{
		Insert(_head->_next, newspan); //头插在第一个有效的Span前
	}

	~SpanList()
	{

	}

private:
	Span* _head; //第一个Span的指针 , 当做哨兵位，底下没有内存块
public:
	std::mutex _mtx; //“木板锁”, 多个线程同时向该木板申请时，对该木板SpanList加锁
};

